/*struct FileDescriptor {
	char fileName[50];
	char filePath[100];
	char fileType[5];
	int size;
	//Location Block Number
};
*/
struct BST_node{
	char fileName[50];
	struct BST_node * leftChild;
	struct BST_node * rightSibling;
};
/*
void copyString (char *str1, char *str2) {
	int i = 0;
	//str1 = (char *) malloc (50 * sizeof(char));
	while (*(str2 + i) && (*(str2 + i) != '\n')){
		*(str1 + i) = *(str2 + i);
		i++;
	}
	*(str1 + i) = '\0';
}

char *split(char *fname) {
	char str[50], *str1;
	str1 = (char *) malloc (sizeof(fname));
	int i = 0, j = 0;	
	if(fname[i] == '/')
		i = 1;
	while (*(fname + i) != '/' && *(fname + i)) {
		*(str + j) = *(fname + i);
		i++;
		j++;
	}
	*(str + j) = '\0';
	copyString(str1, str);
	return str1;
}

char *truncateLeft(char *fn, int length) {
	fn = fn + length + 1;
	return fn;
}

int stringLength (char *str) {
	int i = 0;
	while(*(str + i))
		i++;
	return i;
}
*/
struct BST_node *insertBSTNode (struct BST_node *root,char *fname) {
	char *fn, *fileName;
	struct BST_node *temp = root;
	struct BST_node *newNode, *temp1, *parent;
	fileName = fname;
	newNode = (struct BST_node *) malloc (sizeof(struct BST_node));
	//newNode -> fileName = '\0';
	newNode -> leftChild = NULL;
	newNode -> rightSibling = NULL;
	if (temp == NULL){
		root = newNode;
		fn = split(fname);
		copyString(root -> fileName, fn);
		root = insertBSTNode (root, fileName);
	}
	else {
		fn = split(fname);
		parent = temp;
		while (temp){
			temp1 = temp;
			if ( !strcmp(temp -> fileName, fn)) {
				parent = temp;
				if (temp -> leftChild) {
					temp = temp -> leftChild;
					fname = truncateLeft (fname, stringLength(fn));
					fn = split (fname);
				}
				else {
					fname = truncateLeft (fname, stringLength(fn));
					fn = split (fname);
					if(*fn){
						parent -> leftChild = newNode;
						copyString(newNode -> fileName, fn);
						root = insertBSTNode (root, fileName);
					}
				}
			}
			else {
				/*
				if (temp == root && temp -> rightSibling == NULL){
					temp1 -> rightSibling = newNode;
					copyString(newNode -> fileName, fn);
					root = insertNode (root, fileName);
				}
				*/
				temp = temp -> rightSibling;
			}
		}
		if(temp1 != parent) {
			temp1 -> rightSibling = newNode;
			copyString(newNode -> fileName, fn);
			root = insertBSTNode (root, fileName);
		}
	}
	return root;
}
/*
node *nextPredecessor (node *current) {
	node *temp = current, *preNode;
	if (temp -> leftChild) {
		preNode = temp;
		temp = temp -> leftChild;
		while (temp -> rightSibling) {
			preNode = temp;
			temp = temp -> rightSibling;
		}
		if (preNode -> fileName != current -> fileName)
			preNode -> rightSibling = temp -> leftChild;
		else
			preNode -> leftChild = temp -> leftChild;
		return temp;
	}
	else
		return NULL;
}

node *nextSuccessor (node *current) {
	node *temp = current, *preNode;
	if (temp -> rightSibling) {
		preNode = temp;
		temp = temp -> rightSibling;
		while (temp -> leftChild) {
			preNode = temp;
			temp = temp -> leftChild;
		}
		if (preNode -> fileName != current -> fileName)
			preNode -> leftChild = temp -> rightSibling;
		else
			preNode -> rightSibling = temp -> rightSibling;
		return temp;
	}
	else
		return nextPredecessor(current);
}

node *deleteNode (node *root, int x) {
	node *temp = root;
	node *nextSucc, *preNode, *temp1;
	
	while (temp){
		temp1 = temp;
		if (x < temp -> fileName)
			temp = temp -> leftChild;
		else if ( x > temp -> fileName)
			temp = temp -> rightSibling;
		else {
			nextSucc = nextSuccessor(temp);
			if (preNode -> fileName < temp -> fileName)
				preNode -> rightSibling = nextSucc;
			else
				preNode -> leftChild = nextSucc;
			if (nextSucc) {
				nextSucc -> leftChild = temp -> leftChild;
				nextSucc -> rightSibling = temp -> rightSibling;
			}
			free (temp);
			break;
		}
		preNode = temp1;
	}
	return root;
}

void searchNode (node *root, int x) {
	node *temp = root;
	
	while (temp){
		if (temp -> fileName > x)
			temp = temp -> leftChild;
		else if (temp -> fileName < x)
			temp = temp -> rightSibling;
		else if (temp -> fileName == x) {
			printf ("\nItem %d found\n", x);
			return;
		}
	}
	printf ("\nItem %d not found\n", x);
}
*/
int searchBSTNode (struct BST_node *root,char *fname) {

	char *fn,*fileName;
	struct BST_node *temp;
	temp = root;
	if(root == NULL) {
		printf("Tree has no elements \n");
		return 0;
	}
	else {
		fn = split(fname);
		while(temp) {
			if ( !strcmp(temp -> fileName, fn)) {//compare the file names ...if matches ..take left child	
				fname = truncateLeft (fname, stringLength(fn));
				fn = split (fname);
				if(temp->leftChild && strcmp(fn, "")) {
					temp = temp -> leftChild;
										
				}
				else {
					if(!strcmp(fn, "")) {
						printf("file name found \n");
						return 1;		
					}
					else {
						printf("File doesn't Exist \n");
						return 0;
					}
				}
			}
			else {		//if not ..take right child
				temp = temp->rightSibling;
			}
		}
		printf("file doesn't exist \n");
		return 0 ;
	}	
}


void inOrder2 (struct BST_node *root) {
	if (root == NULL)
		return;
	inOrder (root -> leftChild);
	printf("%s\n", root -> fileName );
	inOrder (root -> rightSibling);
}

void preOrder2 (struct BST_node *root) {
	if (root == NULL)
		return;
	printf("%s\n", root -> fileName );
	preOrder (root -> leftChild);
	preOrder (root -> rightSibling);
}

void postOrder2 (struct BST_node *root) {
	if (root == NULL)
		return;
	postOrder (root -> leftChild);
	postOrder (root -> rightSibling);
	printf("%s\n", root -> fileName );
}
/*
int main() {
	struct BST_node *root = NULL;
	root = insertNode (root, "/home/abc1/a.txt");
	root = insertNode (root, "/home/abc1/b.txt");
	root = insertNode (root, "/home/abc1/d.txt");
	root = insertNode (root, "/home/abc1/e.txt");
	root = insertNode (root, "/home/abc3/a1.txt");
	root = insertNode (root, "/home/abc3/a2.txt");
	root = insertNode (root, "/home/abc3/a3.txt");
	//root = insertNode (root, "/user/abc1/abb.txt");
	//root = insertNode (root, "/user/abc1/a.txt");
	printf("\nPre Order \n");
	preOrder (root);
	printf("\nIn Order \n");
	inOrder (root);
	printf("\nPost Order \n");
	postOrder (root);
	//deleteNode (root, 4);
	/*printf("\nPre Order \n");
	preOrder (root);
	printf("\nIn Order \n");
	inOrder (root);
	printf("\nPost Order \n");
	postOrder (root);*/
/*	searchNode (root, "/home/abc3/a2.txt");
	searchNode (root, "/home/abc3/b3.txt");
	searchNode (root, "/home/abc3");
	searchNode (root, "/home/abc1");
	searchNode (root, "/home");

	//searchNode (root, 9);
	return 0;
}*/
